#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class ZMatch:
    def __init__(self, s):
        self.s = s
        self.l = len(self.s)
        self.z_calc()
        print(self.z_table)

    def z_calc(self):
        self.z_table = self.l * [0]
        left = 1

        # print('left')
        while left < self.l:
            matched_cnt = self._match_from(left)
            self.z_table[left] = matched_cnt
            print('left %s' % left)
            print('matched_cnt %s' % matched_cnt)
            if matched_cnt in [0, 1]:
                # 生成[L, R)
                left += 1
            else:
                # 根据[L, R) 快速往后处理
                right = left + matched_cnt              # [left, right)

                update_to = self._try_update_after(left, right)
                left = update_to

    def _match_from(self, z_from, origin_from=0):
        origin_to = origin_from
        z_to = z_from

        while z_to < self.l:
            if self.s[origin_to] != self.s[z_to]:
                break
            origin_to += 1
            z_to += 1

        # return last not match
        return z_to - z_from

    def _try_update_after(self, left, right):
        # return right作为上层最新left
        # [left, right)
        assert right <= self.l
        cur_match_cnt = self.z_table[left]
        assert right - left == cur_match_cnt

        cur_idx = left + 1
        while cur_idx < right:
            # cur_idx = left + i
            offset = cur_idx - left
            match_to = cur_idx + self.z_table[offset]       # [left+i, match_to) 开闭区间
            print('cur_idx %s' % cur_idx)

            if match_to < right:
                # 在right之前, 一定没有到达字符串边界
                self.z_table[cur_idx] = self.z_table[offset]
            else:
                # 超过right边界, 从right开始匹配(包括超过边界情况)
                # assert match_to >= right
                matched_cnt = right - cur_idx
                aug_matched_cnt = self._match_from(z_from=right, origin_from=right - cur_idx)
                self.z_table[cur_idx] = matched_cnt + aug_matched_cnt
                left = cur_idx
                # if aug_matched_cnt > 0:
                #     print('aug hit %s' % self.z_table[cur_idx])
                # right = cur_idx + matched_cnt + aug_matched_cnt # 如果aug_matched_cnt > 0 则更新right, 否则计算出来还是原值
                right = right + aug_matched_cnt # 如果aug_matched_cnt > 0 则更新right, 否则计算出来还是原值

            cur_idx += 1

        return right


class ZMatchOld:
    def __init__(self, s):
        self.s = s
        self.l = len(self.s)
        self.z_calc()
        print(self.z_table)

    def z_calc(self):
        self.z_table = self.l * [0]
        left = 1

        print('left')
        while left < self.l:
            matched_cnt = self._match_from(left)
            self.z_table[left] = matched_cnt
            print('left %s' % left)
            print('matched_cnt %s' % matched_cnt)
            if matched_cnt == 0:
                left += 1
            else:
                # print('left %s' % left)
                right = left + matched_cnt              # [left, right)

                update_to = self._try_update_after(left, right)
                left = update_to

    def _match_from(self, z_from, origin_from=0):
        origin_to = origin_from
        z_to = z_from

        while z_to < self.l:
            if self.s[origin_to] != self.s[z_to]:
                break
            origin_to += 1
            z_to += 1

        # return last not match
        return z_to - z_from

    def _try_update_after(self, left, right):
        # return update_to idx
        # [left, right)
        assert right <= self.l
        cur_match_cnt = self.z_table[left]
        assert right - left == cur_match_cnt

        for i in range(1, cur_match_cnt):
            cur_idx = left + i
            match_to = left + i + self.z_table[i]       # [left+i, match_to) 开闭区间
            print('cur_idx %s' % cur_idx)

            if match_to < right:
                # 在right之前, 一定没有到达字符串边界
                self.z_table[cur_idx] = self.z_table[i]

            # elif match_to > self.l:
            #     self.z_table[cur_idx] = self.l - cur_idx
            #     # 超过字符边界, 从right开始匹配(包括超过边界情况)

            else:
                # 超过right边界, 从right开始匹配(包括超过边界情况)
                # matched_cnt = self.z_table[i]
                # assert match_to >= right
                matched_cnt = right - cur_idx
                aug_matched_cnt = self._match_from(z_from=right, origin_from=right - cur_idx)
                self.z_table[cur_idx] = matched_cnt + aug_matched_cnt


        return right


def main():
    print("start main")
    z = ZMatch('aabxaabxcaabxaabxay')
    z = ZMatch('aaaaa')
    z = ZMatch('aaaaaaaaaa')
    z = ZMatch('aaaab')

if __name__ == "__main__":
    main()
